模拟赛题解/2025.9.25 模拟赛

T1-微光（glow）

题面

你设计了一种新的屏保——也是一些彩色的泡泡。为了简化模型，你决定从一维上的问题下手：你现在有一根长为 $L$ 米的线段，在上面有 $n$ 个泡泡，每个泡泡以 $1$ 米/秒的速度，匀速沿着线段，在两个可能方向中的一个方向上移动，并以可能的 $k$ 种颜色中的其中一种着色。

你设定：如果一个泡泡和另一个泡泡相碰，则该泡泡会改变方向，向着相反的方向以相同速度继续运动。此外，向左运动的颜色为 $a$ 的泡泡和向右运动颜色为 $b$ 的泡泡发生碰撞后，先前向左的泡泡的颜色会变成 $b$，而先前向右的泡泡颜色变为 $(a+b)\bmod k$。

给你所有泡泡的初始位置、颜色、运动方向，对于每种颜色，确定所有泡泡以该种颜色着色在离开线段前运动的总行程。

$1\leq n\leq10^5,1\leq k\leq40,1\leq L\leq10^6,0\leq b_i\leq L,0\leq d_i<k$。

题解

改变方向太麻烦了，考虑不改变点的移动方向。

问题就转化成两个点相遇后继续向前，其中向右的点颜色不变，向左的点改为二者颜色之和。

于是向右的点的总权值是容易统计的。

向左的点可以考虑模拟这个过程，但是基于点模拟太慢了，可以基于颜色模拟，记忆每种颜色有几个点。

遇到向左的点就加入，向右的点就更改，因为 $k$ 相当小所以可以暴力修改。

于是直接得到一个 $O(nk)$ 的暴力做法。

T2-泪雨（namidame）

题面

给定小写英文字母和 ? 组成的字符串 $s$。

“泪雨” 定义为这样的串：这是一个回文串，并且 ? 的个数大于等于小写英文字符的个数。

请对于是 “泪雨” 的 $s$ 的所有子串，求出它们问号位置的和之和。（位置下标从 $1$ 开始）

形式化题意：定义：

$$f(l,r)=\sum_{i=l}^r[s_i='?']\cdot i\\ g(l,r)=\left[\sum_{i=l}^r[s_i='?']\geq \frac{r-l+1}2\right]\cdot\prod_{i=l}^{\frac{l+r}2}[s_i=s_{l+r-i}]$$

请你求 $\sum_{l=1}^n\sum_{r=l}^ng(l,r)\cdot f(l,r)$，其中 $n=|s|$。

$1\leq n\leq5\times10^6$。

题解

先找出回文串然后考虑如何算贡献。

对于一个符合泪雨性质的子串，我们注意到因为它是一个回文串，所以其问号的位置之和即为问号数量乘以其中心位置。

而 $\text{manacher}$ 维护的就是对于一个点，以其为中心的最大回文串长度。

所以可以考虑在 $\text{manacher}$ 过程中维护以该点为中心的所有“泪雨”串的问号数量之和。

对于一个点，我们可以跟 $\text{manacher}$ 一样从其对称点进行转移。

考虑到可能出现超出当前右边界的情况，我们注意到可以直接向内减小字符串，于是暴力收缩。

这样的复杂度其实是正确的。记回文半径为 $d_i$，从 $p_i=2\times mid − i$ 处转移，我们考虑当前最右的区间 $[l,r]$，我们在 $i+d_i\geq r$ 时就更新回文区间和对应中心。当 $i+d_{p_i}>r$ 时发生收缩，总的收缩长度：

$$\sum i+d_{p_i}−r\leq\sum i+(r−p_i)−r=\sum i−p_i=\sum 2(mid − i)$$

如果发生了收缩，$mid$ 就会变成 $i$，所以 $\sum2(mid−i)\leq2n$，复杂度是对的。

复杂度均摊 $O(n)$。

T3-深海（sort）

题面

小葱很好奇一个序列冒泡排序 $k$ 轮之后的样子，具体地说，对于一个长度为 $1\sim n$ 的排列 $a_i$，她有两种询问：

1 给定 $l,r,k,x$，求将 $a$ 的区间 $[l,r]$ 冒泡排序 轮之后，$x$ 这个数在数组中的下标。 2 给定 $l,r,k,x$，求将 $a$ 的区间 $[l,r]$ 冒泡排序 轮之后，$a_x$ 的值。

定义对 $\{a_i\}$ 的区间 进行一轮冒泡排序为：依次对 $i=l,l+1,\cdots,r-1$ 操作，若 $a_i>a_{i+1}$ 则交换 $a_i,a_{i+1}$。

注意询问中的排序操作并不实际在 $a$ 上生效，也就是说询问之间互相独立。小葱不会为难你，所以对于单个测试点，所有询问都是同一种。

$1\leq n,q\leq6\times10^5,o\in{1,2},1\leq l,r\leq n,1\leq x\leq n,0\leq k\leq n-1$。

题解

O=2

研究排序问题时（尤其是排列），可以先进行值域压缩：通常我们会把序列变成 $0$-$1$ 序列，比较特殊的时候还会有压缩成 $[-1,1]$ 或其它更大一点值域的需求，在此不展开。

我们二分值域，随后把序列变成 $a_i' = [a_i \geq mid]$，接下来只需要判定询问的位置是 $1$ 还是 $0$。

考虑刻画一下冒泡排序的操作。对于下标从 $1$ 到 $n$ 的序列：

现在 $1$ 之间没有区别，我们完全可以让最左边的那个 $1$ 不断交换到最后，也相当于把最左边的 $1$ 之后的下标减 $1$ 再把它的下标设成 $n$。注意一些边界，那么判定就是很简单的：

• 如果 $k \geq$ 序列中 $1$ 的个数，那么显然序列已经排序完了。（不用特别划这个）
• 如果 $x+k > n$，那就说明出时它在长度为 $k$ 的后缀上，只需要判断 $1$ 的数量是否足够。
• 其余情况，我们只用数一下 $x+k$ 前面有多少个 $1$，若只有 $\leq k-1$，则答案显然就是 $0$；否则，答案就是绕过了长轮子移后到达 $x$ 位置：$a_{x+k}''$。

对于区间询问，进行主席树上二分即可做到 $O((n+q)\log n)$。

O=1

由于涉及了具体的位置，我们不妨把值域压缩成 $[-1,1]$ 再观察（其实可以脱离值域压缩观察，因为只涉及和 $x$ 比大小）。我们考虑 $0$ 的动作。

首先，当前面有1时，和 $o=2$ 一样，它的行为和 $-1$ 一致，每次会向前移动一步；当前面没有1的时候，它向后冒泡，直到遇见一个1，之后这个1就会向后冒泡。

同样地，考虑形式化这个东西：

• 如果 $\geq$ 序列中 $0,1$ 的个数，那么显然序列已经排序完了。
• 先统计现在 $x$ 的位置前有多少个1，记为 $c, c \geq k$ 的情况是平凡的，现在还要向后移动 $k$ 次，代表我们要找到从左到右数的第 $k$ 个1的位置，计算答案直接做。
• 否则较复杂，换句话考虑，考虑后面有多少个1会移到它前面，就是要知道的是从 $x$ 的位置到 $p+c-1$，这样就做完了。

这一部分可以离线后扫扫描线，主席树即可。

时间复杂度 $O((n+q)\log n)$。

T4-虚无（nihility）

题面

你正在玩一种智力游戏，你需要让在迷宫起点处的棋子到达终点。

坐拥上帝视角的你已经知道了迷宫的全貌，这是一个 $n$ 个点 $m$ 条边的有向图，每条边有一个颜色 $c_i$，一个点连出的边颜色都不相同，且图中所有边的颜色只有 $k$ 种。为了方便，我们把起点标号为 $0$，而终点为 $n-1$。

这个游戏的流程是这样的：你有一个牌堆，在游戏最开始的时候，你可以向牌堆里加入任意多的牌，每张牌有颜色，颜色由你决定（在 $0\sim k-1$ 中）。随后游戏开始：

假设当前棋子处在点 $u$，当前牌堆顶的牌颜色为 $c$：

1 如果 $u$ 向某个点 $v$ 连了一条颜色为 $c$ 的边，就把棋子向点 $v$ 移动，并丢弃牌堆顶的这张牌。 2 否则，若牌堆为空或者不存在一条出边颜色为 $c$，你可以把棋子沿着该点任意一条出边移动。如果选择了一条颜色为 $d$ 的边，则会在牌堆顶加入一张颜色为 $d$ 的卡牌。

为了让游戏有挑战性，你想要让初始牌堆的牌数目尽可能少。你只需要求出这个最少的数目。

$1\leq n\leq50,2\leq m\leq100,1\leq k\leq20$，对于输入的每条边 $(u,v,w)$，保证 $0\leq u,v\leq n-1,0\leq w\leq k-1,u\not=v$。

题解

如果可达，那么答案必然 $\leq n-1$，考虑在起点前加一些“没有限制”的虚点，以此使得可以在起点 $0$ 获得所有可能方案，我们这样连边：

• 对于 $n$ 号点，向 $0$ 连所有颜色的边。
• 对于 $n+i \ (1 \leq i \leq n-1)$ 向 $n+i-1$ 连所有颜色的边。

没有限制的意思就是说：这些边只负责加牌，而不执行操作 $1$。

这样如果我们能够从虚点 $u$ 以空栈状态到达 $n-1$，答案就是 $u \to (n-1)$（若从 $0$ 能到答案就是 $0$）。

现在问题转化成了一个可达性问题，我们只需要判定是否空栈地从起点，以空栈的状态到达终点。

注意空栈任选走边加牌到非空栈时强制走边这个过程比较特殊，我们需要在状态里加入这个信息。

记 $f_{i,j,c}$ 表示，存在一条路径使得空栈状态的 $i$ 可以到达空栈状态 $j$，且，路径中不存在在一个空栈的时候有颜色为 $c$ 的出边。转移考虑类似括号序列生成的转移。

第一种转移形似传递闭包，也可看作把两个括号序列拼在一起：$f_{i,j,c} \leftarrow f_{i,k,c} \wedge f_{k,j,c}$

第二种转移仅在括号序列两侧加一对括号：如果 $i$ 有一条颜色为 $c$ 的入边 $(u,i)$，$j$ 有一条颜色为 $c$ 的出边 $(j,v)$，且 $u$ 不存在一条颜色为 $c'$ 的出边， $f_{u,v,c'} \leftarrow f_{i,j,c}$。

注意此类转移对我们建的虚点也生效，因为它们没有要强制定之类的限制，也就是 $u > n-1$ 时也执行转移。

注意一种情况：当前可能用满所有颜色边的时候（其实就是 $0$ 连出了所有颜色的边的时候），我们新建一个颜色 $k_c$，即用解作这种情况。

转移顺序比较复杂，使用记忆化搜索即可。时间复杂度 $O\left((n^2 + nk + mk)nk\right)$。